#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <stdexcept>
#include <string>

enum TokenType {
    KW,            // Keyword
    IDN,           // Identifier
    OP,            // Operator
    SE,            // Separator
    INT_LITERAL,   // Integer literal
    FLOAT_LITERAL, // Floating-point literal
    END            // End of input marker
};

struct Token {
    std::string lexeme;    // The exact string from source
    TokenType    type;     // Token category
    std::string  attribute; // Additional attribute (e.g., keyword value or literal text)
};

using namespace std;

// Global token stream and pointer
static vector<Token> tokens;
static size_t current = 0;
static ofstream outputFile;
static int step = 1;

// First and Follow sets
static map<string, set<string>> firstSets = {
    {"program",    {"const", "int", "float", "void", "main"}},
    {"compUnit",   {"const", "int", "float", "void", "main"}},
    {"decl",       {"const", "int", "float"}},
    {"constDecl",  {"const"}},
    {"varDecl",    {"int", "float"}},
    {"bType",      {"int", "float"}},
    {"funcType",   {"void", "int", "float"}},
    {"block",      {"{"}},
    {"blockItem",  {"const", "int", "float", "if", "return", "{", "IDN", ";", "main"}},
    {"stmt",       {"if", "return", "{", "IDN", "INT", "FLOAT", "(", ";", "main"}},
    {"exp",        {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"cond",       {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"lVal",       {"IDN"}},
    {"primaryExp", {"(", "IDN", "INT", "FLOAT", "main"}},
    {"number",     {"INT", "FLOAT"}},
    {"unaryExp",   {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"unaryOp",    {"+", "-", "!"}},
    {"mulExp",     {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"addExp",     {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"relExp",     {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"eqExp",      {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"lAndExp",    {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"lOrExp",     {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}},
    {"constExp",   {"(", "IDN", "INT", "FLOAT", "+", "-", "!", "main"}}
};

static map<string, set<string>> followSets = {
    {"program",    {"EOF"}},
    {"compUnit",   {"EOF"}},
    {"decl",       {"const", "int", "float", "void", "if", "return", "{", "}", "IDN", ";", "main", "EOF"}},
    {"bType",      {"IDN"}},
    {"block",      {"else", "const", "int", "float", "void", "if", "return", "{", "}", "IDN", ";", "main", "EOF"}},
    {"stmt",       {"else", "const", "int", "float", "void", "if", "return", "{", "}", "IDN", ";", "main"}}
};

// Helper functions for set checking
static bool inFirst(const string& nonTerminal, const Token& tok) {
    if (firstSets[nonTerminal].count(tok.lexeme)) return true;

    // 处理类型符号（IDN, INT, FLOAT）
    if (tok.type == IDN && firstSets[nonTerminal].count("IDN")) return true;
    if (tok.type == INT_LITERAL && firstSets[nonTerminal].count("INT")) return true;
    if (tok.type == FLOAT_LITERAL && firstSets[nonTerminal].count("FLOAT")) return true;

    return false;
}

static bool inFollow(const string& nonTerminal, const Token& tok) {
    return followSets[nonTerminal].count(tok.lexeme) || 
           (tok.type == END && followSets[nonTerminal].count("EOF"));
}

// Output the reduction sequence
void outputReduction(const string& topSymbol, const string& nextToken, const string& action) {
    string nextTokenStr = nextToken.empty() ? "EOF" : nextToken;
    outputFile << step << "\t" << topSymbol << "#" << nextTokenStr << "\t" << action << endl;
    step++;
}

// Helpers
static Token peek() {
    if (current >= tokens.size()) return Token{"", END, ""};
    return tokens[current];
}

static Token advanceTok() {
    if (current >= tokens.size()) return Token{"", END, ""};
    return tokens[current++];
}

static bool match(const vector<string>& opts) {
    for (auto& s : opts) {
        if (peek().lexeme == s) { 
            outputReduction(s, peek().lexeme, "move");
            advanceTok(); 
            return true; 
        }
    }
    return false;
}

static void error(const string& msg) {
    outputReduction("ERROR", peek().lexeme, "error");
    ostringstream oss;
    oss << "Syntax error at token '" << peek().lexeme << "': " << msg;
    throw runtime_error(oss.str());
}

// Forward declarations for grammar rules
void program();
void compUnit();
void decl();
void constDecl();
void bType();
void constDef();
void constInitVal();
void constExp();
void varDecl();
void varDef();
void initVal();
void funcDef();
void funcType();
void funcFParams();
void funcFParam();
void block();
void blockItem();
void stmt();
string exp();
string cond();
string lVal();
string primaryExp();
string number();
string unaryExp();
string unaryOp();
void funcRParams();
string funcRParam();
string mulExp();
string addExp();
string relExp();
string eqExp();
string lAndExp();
string lOrExp();

// Entry
bool runParser(const vector<Token>& inputTokens, const string& outputFilename) {
    tokens = inputTokens;
    current = 0;
    step = 1;
    
    outputFile.open(outputFilename);
    if (!outputFile.is_open()) {
        cerr << "Error: Could not open output file " << outputFilename << endl;
        return false;
    }
    
    try {
        program();
        
        if (peek().type != END) {
            error("Extra tokens after program end");
        } else {
            outputReduction("END", "EOF", "accept");
        }
    } catch (const runtime_error& e) {
        cerr << e.what() << endl;
        outputFile.close();
        return false;
    }
    
    outputFile.close();
    cout << "Parsing completed successfully. Output written to " << outputFilename << endl;
    return true;
}

// 1. Program -> compUnit
void program() {
    outputReduction("program", peek().lexeme, "reduction");
    compUnit();
}

// 2. compUnit -> (decl | funcDef)* EOF
void compUnit() {
    outputReduction("compUnit", peek().lexeme, "reduction");
    
    while (peek().type != END) {
        // 处理main函数定义的特殊情况
        if (peek().lexeme == "main") {
            // 如果直接看到main，可能是语法错误
            error("Expected type before 'main'");
        }
        
        // 根据下一个token判断是声明还是函数定义
        if (peek().lexeme == "const" || peek().lexeme == "int" || peek().lexeme == "float") {
            // 保存当前位置
            size_t savedPos = current;
            
            // 跳过const/int/float
            Token typeToken = advanceTok();
            
            // 如果是"const"，那一定是声明
            if (typeToken.lexeme == "const") {
                current = savedPos;
                decl();
                continue;
            }
            
            // 检查是否有标识符
            if (peek().type == IDN) {
                // 记住标识符
                string identName = peek().lexeme;
                advanceTok();
                
                // 如果下一个是'('，则是函数定义
                if (peek().lexeme == "(") {
                    current = savedPos;
                    funcDef();
                } else {
                    // 否则是声明
                    current = savedPos;
                    decl();
                }
            } else if (peek().lexeme == "main") {
                // 特殊处理main函数
                current = savedPos;
                funcDef();
            } else {
                // 恢复位置，可能遇到语法错误
                current = savedPos;
                error("Expected identifier after type");
            }
        } else if (peek().lexeme == "void") {
            // void只能是函数返回类型
            funcDef();
        } else {
            error("Expected declaration or function definition");
        }
    }
}

// 3. decl -> constDecl | varDecl
void decl() {
    outputReduction("decl", peek().lexeme, "reduction");
    
    if (peek().lexeme == "const") {
        constDecl();
    } else if (peek().lexeme == "int" || peek().lexeme == "float") {
        varDecl();
    } else {
        error("Expected 'const', 'int', or 'float'");
    }
}

// 4. constDecl -> 'const' bType constDef (',' constDef)* ';'
void constDecl() {
    outputReduction("constDecl", peek().lexeme, "reduction");
    
    if (!match({"const"})) error("Expected 'const'");
    bType();
    
    constDef();
    
    while (match({","})) {
        constDef();
    }
    
    if (!match({";"})) error("Expected ';' after const declaration");
}

// 5. bType -> 'int' | 'float'
void bType() {
    outputReduction("bType", peek().lexeme, "reduction");
    
    if (!match({"int", "float"})) {
        error("Expected 'int' or 'float'");
    }
}

// 6. constDef -> Ident '=' constInitVal
void constDef() {
    outputReduction("constDef", peek().lexeme, "reduction");
    
    if (peek().type != IDN) error("Expected identifier");
    outputReduction("Ident", peek().lexeme, "move");
    advanceTok();
    
    if (!match({"="})) error("Expected '=' after identifier in const definition");
    
    constInitVal();
}

// 7. constInitVal -> constExp
void constInitVal() {
    outputReduction("constInitVal", peek().lexeme, "reduction");
    constExp();
}

// 33. constExp -> addExp
void constExp() {
    outputReduction("constExp", peek().lexeme, "reduction");
    addExp();
}

// 8. varDecl -> bType varDef (',' varDef)* ';'
void varDecl() {
    outputReduction("varDecl", peek().lexeme, "reduction");
    
    bType();
    varDef();
    
    while (match({","})) {
        varDef();
    }
    
    if (!match({";"})) error("Expected ';' after variable declaration");
}

// 9. varDef -> Ident | Ident '=' initVal
void varDef() {
    outputReduction("varDef", peek().lexeme, "reduction");
    
    if (peek().type != IDN) error("Expected identifier");
    outputReduction("Ident", peek().lexeme, "move");
    advanceTok();
    
    // 可选的初始化
    if (match({"="})) {
        initVal();
    }
}

// 10. initVal -> exp
void initVal() {
    outputReduction("initVal", peek().lexeme, "reduction");
    exp();
}

// 11. funcDef -> funcType Ident '(' (funcFParams)? ')' block
void funcDef() {
    outputReduction("funcDef", peek().lexeme, "reduction");
    
    funcType();
    
    // Handle both regular identifiers and 'main'
    if (peek().type == IDN) {
        outputReduction("Ident", peek().lexeme, "move");
        advanceTok();
    } else if (peek().lexeme == "main") {
        outputReduction("Ident", peek().lexeme, "move");
        advanceTok();
    } else {
        error("Expected identifier or 'main' for function name");
    }
    
    if (!match({"("})) error("Expected '(' after function name");
    
    // 可选的函数参数
    if (peek().lexeme != ")") {
        funcFParams();
    }
    
    if (!match({")"})) error("Expected ')' after function parameters");
    
    block();
}

// 12. funcType -> 'void' | 'int' | 'float'
void funcType() {
    outputReduction("funcType", peek().lexeme, "reduction");
    
    if (!match({"void", "int", "float"})) {
        error("Expected 'void', 'int', or 'float' for function return type");
    }
}

// 13. funcFParams -> funcFParam (',' funcFParam)*
void funcFParams() {
    outputReduction("funcFParams", peek().lexeme, "reduction");
    
    funcFParam();
    
    while (match({","})) {
        funcFParam();
    }
}

// 14. funcFParam -> bType Ident
void funcFParam() {
    outputReduction("funcFParam", peek().lexeme, "reduction");
    
    bType();
    
    if (peek().type != IDN) error("Expected identifier for parameter name");
    outputReduction("Ident", peek().lexeme, "move");
    advanceTok();
}

// 15. block -> '{' (blockItem)* '}'
void block() {
    outputReduction("block", peek().lexeme, "reduction");
    
    if (!match({"{"})) error("Expected '{' at start of block");
    
    while (peek().lexeme != "}") {
        blockItem();
    }
    
    if (!match({"}"})) error("Expected '}' at end of block");
}

// 16. blockItem -> decl | stmt
void blockItem() {
    outputReduction("blockItem", peek().lexeme, "reduction");
    
    if (peek().lexeme == "const" || peek().lexeme == "int" || peek().lexeme == "float") {
        decl();
    } else {
        stmt();
    }
}

// 17. stmt -> lVal '=' exp ';' | (exp)? ';' | block | 'if' '(' cond ')' stmt ('else' stmt)? | 'return' (exp)? ';'
void stmt() {
    outputReduction("stmt", peek().lexeme, "reduction");
    
    if (peek().lexeme == "if") {
        // if语句
        if (!match({"if"})) error("Expected 'if'");
        if (!match({"("})) error("Expected '(' after 'if'");
        cond();
        if (!match({")"})) error("Expected ')' after condition");
        stmt();
        
        // 可选的else分支
        if (peek().lexeme == "else") {
            if (!match({"else"})) error("Expected 'else'");
            stmt();
        }
    } 
    else if (peek().lexeme == "return") {
        // return语句
        if (!match({"return"})) error("Expected 'return'");
        
        // 可选的返回表达式
        if (peek().lexeme != ";") {
            exp();
        }
        
        if (!match({";"})) error("Expected ';' after return statement");
    } 
    else if (peek().lexeme == "{") {
        // 代码块
        block();
    } 
    else if (peek().lexeme == ";") {
        // 空语句
        if (!match({";"})) error("Expected ';'");
    } 
    else {
        // 可能是赋值语句或表达式语句
        
        // 保存当前位置
        size_t savedPos = current;
        
        try {
            // 尝试解析赋值语句
            string identName = lVal();
            
            if (match({"="})) {
                // 赋值语句
                exp();
                if (!match({";"})) error("Expected ';' after assignment");
                return;
            } else {
                // 不是赋值语句，回退
                current = savedPos;
            }
        } catch (...) {
            // 解析lVal失败，回退
            current = savedPos;
        }
        
        // 表达式语句
        if (peek().lexeme != ";") {
            exp();
        }
        
        if (!match({";"})) error("Expected ';' after expression");
    }
}

// 18. exp -> addExp
string exp() {
    outputReduction("exp", peek().lexeme, "reduction");
    return addExp();
}

// 19. cond -> lOrExp
string cond() {
    outputReduction("cond", peek().lexeme, "reduction");
    return lOrExp();
}

// 20. lVal -> Ident
string lVal() {
    outputReduction("lVal", peek().lexeme, "reduction");
    
    if (peek().type != IDN) error("Expected identifier");
    string identName = peek().lexeme;
    outputReduction("Ident", identName, "move");
    advanceTok();
    
    return identName;
}

// 21. primaryExp -> '(' exp ')' | lVal | number
string primaryExp() {
    outputReduction("primaryExp", peek().lexeme, "reduction");
    
    if (match({"("})) {
        string type = exp();
        if (!match({")"})) error("Expected ')'");
        return type;
    } 
    else if (peek().type == IDN) {
        return lVal();
    } 
    else {
        return number();
    }
}

// 22. number -> IntConst | floatConst
string number() {
    outputReduction("number", peek().lexeme, "reduction");
    
    if (peek().type == INT_LITERAL) {
        outputReduction("IntConst", peek().lexeme, "move");
        advanceTok();
        return "int";
    } 
    else if (peek().type == FLOAT_LITERAL) {
        outputReduction("floatConst", peek().lexeme, "move");
        advanceTok();
        return "float";
    } 
    else {
        error("Expected integer or float constant");
        return "";
    }
}

// 23. unaryExp -> primaryExp | Ident '(' (funcRParams)? ')' | unaryOp unaryExp
string unaryExp() {
    outputReduction("unaryExp", peek().lexeme, "reduction");
    
    if (peek().type == IDN) {
        // 保存当前位置
        size_t savedPos = current;
        
        // 检查是否是函数调用
        string identName = peek().lexeme;
        advanceTok();
        
        if (peek().lexeme == "(") {
            // 函数调用
            outputReduction("Ident", identName, "move");
            if (!match({"("})) error("Expected '('");
            
            // 可选的函数参数
            if (peek().lexeme != ")") {
                funcRParams();
            }
            
            if (!match({")"})) error("Expected ')'");
            return "int"; // 假设返回类型为int，实际应根据函数声明确定
        } else {
            // 不是函数调用，回退
            current = savedPos;
            return primaryExp();
        }
    } 
    else if (peek().lexeme == "+" || peek().lexeme == "-" || peek().lexeme == "!") {
        // 一元操作符表达式
        unaryOp();
        return unaryExp();
    } 
    else {
        // 主表达式
        return primaryExp();
    }
}

// 24. unaryOp -> '+' | '-' | '!'
string unaryOp() {
    outputReduction("unaryOp", peek().lexeme, "reduction");
    
    if (!match({"+", "-", "!"})) {
        error("Expected unary operator '+', '-', or '!'");
    }
    return "operator";
}

// 25. funcRParams -> funcRParam (',' funcRParam)*
void funcRParams() {
    outputReduction("funcRParams", peek().lexeme, "reduction");
    
    funcRParam();
    
    while (match({","})) {
        funcRParam();
    }
}

// 26. funcRParam -> exp
string funcRParam() {
    outputReduction("funcRParam", peek().lexeme, "reduction");
    return exp();
}

// 27. mulExp -> unaryExp | mulExp ('*' | '/' | '%') unaryExp
string mulExp() {
    outputReduction("mulExp", peek().lexeme, "reduction");
    
    string ltype = unaryExp();
    
    while (peek().lexeme == "*" || peek().lexeme == "/" || peek().lexeme == "%") {
        string op = peek().lexeme;
        if (!match({"*", "/", "%"})) error("Expected '*', '/', or '%'");
        
        string rtype = unaryExp();
        // 可以在这里添加类型检查逻辑
    }
    
    return ltype;
}

// 28. addExp -> mulExp | addExp ('+' | '-') mulExp
string addExp() {
    outputReduction("addExp", peek().lexeme, "reduction");
    
    string ltype = mulExp();
    
    while (peek().lexeme == "+" || peek().lexeme == "-") {
        string op = peek().lexeme;
        if (!match({"+", "-"})) error("Expected '+' or '-'");
        
        string rtype = mulExp();
        // 可以在这里添加类型检查逻辑
    }
    
    return ltype;
}

// 29. relExp -> addExp | relExp ('<' | '>' | '<=' | '>=') addExp
string relExp() {
    outputReduction("relExp", peek().lexeme, "reduction");
    
    string ltype = addExp();
    
    while (peek().lexeme == "<" || peek().lexeme == ">" || 
           peek().lexeme == "<=" || peek().lexeme == ">=") {
        string op = peek().lexeme;
        if (!match({"<", ">", "<=", ">="})) error("Expected '<', '>', '<=', or '>='");
        
        string rtype = addExp();
        ltype = "bool"; // 关系表达式返回布尔值
    }
    
    return ltype;
}

// 30. eqExp -> relExp | eqExp ('==' | '!=') relExp
string eqExp() {
    outputReduction("eqExp", peek().lexeme, "reduction");
    
    string ltype = relExp();
    
    while (peek().lexeme == "==" || peek().lexeme == "!=") {
        string op = peek().lexeme;
        if (!match({"==", "!="})) error("Expected '==' or '!='");
        
        string rtype = relExp();
        ltype = "bool"; // 相等表达式返回布尔值
    }
    
    return ltype;
}

// 31. lAndExp -> eqExp | lAndExp '&&' eqExp
string lAndExp() {
    outputReduction("lAndExp", peek().lexeme, "reduction");
    
    string ltype = eqExp();
    
    while (peek().lexeme == "&&") {
        if (!match({"&&"})) error("Expected '&&'");
        
        string rtype = eqExp();
        ltype = "bool"; // 逻辑AND表达式返回布尔值
    }
    
    return ltype;
}

// 32. lOrExp -> lAndExp | lOrExp '||' lAndExp
string lOrExp() {
    outputReduction("lOrExp", peek().lexeme, "reduction");
    
    string ltype = lAndExp();
    
    while (peek().lexeme == "||") {
        if (!match({"||"})) error("Expected '||'");
        
        string rtype = lAndExp();
        ltype = "bool"; // 逻辑OR表达式返回布尔值
    }
    
    return ltype;
}

// 辅助函数：从文件读取token
vector<Token> readTokensFromFile(const string& filename) {
    ifstream inFile(filename);
    if (!inFile.is_open()) {
        cerr << "Error: Could not open token file " << filename << endl;
        exit(1);
    }

    vector<Token> tokens;
    string line;
    while (getline(inFile, line)) {
        if (line.empty()) continue;

        // 处理 EOF 或 END
        if (line.find("<EOF>") != string::npos || line.find("<END>") != string::npos) {
            tokens.push_back({"", END, ""});
            break;
        }

        size_t typeStart = line.find('<');
        size_t typeEnd = line.find('>');

        if (typeStart == string::npos || typeEnd == string::npos) {
            cerr << "Error: Malformed token line: " << line << endl;
            exit(1);
        }

        string lexeme = line.substr(0, typeStart);
        lexeme.erase(0, lexeme.find_first_not_of(" \t"));
        lexeme.erase(lexeme.find_last_not_of(" \t") + 1);

        string typeAndLine = line.substr(typeStart + 1, typeEnd - typeStart - 1);
        size_t commaPos = typeAndLine.find(',');

        TokenType type;
        string lineNum;

        if (commaPos != string::npos) {
            string typeStr = typeAndLine.substr(0, commaPos);
            // 去除 typeStr 前后的空格
            typeStr.erase(0, typeStr.find_first_not_of(" \t"));
            typeStr.erase(typeStr.find_last_not_of(" \t") + 1);

            lineNum = typeAndLine.substr(commaPos + 1);
            lineNum.erase(0, lineNum.find_first_not_of(" \t"));
            lineNum.erase(lineNum.find_last_not_of(" \t") + 1);

            if (typeStr == "KW") {
                type = KW;
            } else if (typeStr == "IDN") type = IDN;
            else if (typeStr == "INT") type = INT_LITERAL;
            else if (typeStr == "FLOAT") type = FLOAT_LITERAL;
            else if (typeStr == "OP") type = OP;
            else if (typeStr == "SE") type = SE;
            else if (typeStr == "EOF" || typeStr == "END") type = END;
            else {
                cerr << "Error: Unknown token type: " << typeStr << endl;
                exit(1);
            }
        } else {
            // 处理无逗号的情况（如 EOF）
            string typeStr = typeAndLine;
            typeStr.erase(0, typeStr.find_first_not_of(" \t"));
            typeStr.erase(typeStr.find_last_not_of(" \t") + 1);

            if (typeStr == "EOF" || typeStr == "END") {
                type = END;
            } else {
                cerr << "Error: Malformed type info: " << typeAndLine << endl;
                exit(1);
            }
        }

        tokens.push_back({lexeme, type, lineNum});
    }

    if (tokens.empty() || tokens.back().type != END) {
        tokens.push_back({"", END, ""});
    }

    return tokens;
}

int main() {
    const std::string tokensFile = "tokens.txt";
    const std::string outputFilename = "output.txt";

    // 确保 output.txt 存在，如果不存在则创建一个空文件
    {
        std::ofstream ofs(outputFilename, std::ios::trunc);  // Use trunc to clear the file
        if (!ofs) {
            std::cerr << "无法创建或打开输出文件: " << outputFilename << std::endl;
            return 1;
        }
    }

    // 读取 tokens.txt
    std::vector<Token> tokens;
    try {
        tokens = readTokensFromFile(tokensFile);
    } catch (const std::exception& e) {
        std::cerr << "读取令牌文件失败: " << e.what() << std::endl;
        return 1;
    }

    // 运行解析器并将结果写入 output.txt
    if (!runParser(tokens, outputFilename)) {
        std::cerr << "解析失败" << std::endl;
        return 1;
    }

    std::cout << "解析完成，结果保存在 " << outputFilename << std::endl;
    return 0;
}